import functools


class Solution(object):
    def mctFromLeafValues(self, arr):
        total = sum(arr)

        @functools.cache
        def search(i, j):
            if i == j:
                return arr[i], arr[i]
            else:
                min_t = float('inf')
                for k in range(i, j):
                    left_t, left_v = search(i, k)
                    right_t, right_v = search(k + 1, j)
                    min_t = min(min_t, left_t + right_t + left_v * right_v)
                    max_v = max(left_v, right_v)
                return min_t, max_v
        return search(0, len(arr) - 1)[0] - total


data = Solution()
arr = [6, 2, 4]
print(data.mctFromLeafValues(arr))
